Rotate array

Time: O(N); Space: O(1); easy

Rotate an array of N elements to the right by K steps.

Example 1:

Input: nums=[1,2,3,4,5,6,7], k = 3

Output: [5,6,7,1,2,3,4]

Explanation:

rotate 1 steps to the right: [7,1,2,3,4,5,6] rotate 2 steps to the right: [6,7,1,2,3,4,5] rotate 3 steps to the right: [5,6,7,1,2,3,4]

Example 2:

Input: nums=[-1,-100,3,99], k = 2

Output: [3,99,-1,-100]

Explanation:

rotate 1 steps to the right: [99,-1,-100,3] rotate 2 steps to the right: [3,99,-1,-100]

Notes:

• Try to come up as many solutions as you can, there are at least 3 different ways to solve this problem.

• Could you do it in-place with O(1) extra space?

1. Brute Force

The simplest approach is to rotate all the elements of the array in k steps by rotating the elements by 1 unit in each step.

class Solution1(object):
    """
    Time: O(n×k). All the numbers are shifted by one step (O(n)) k times (O(n)).
    Space: O(1). No extra space is used.
    """
    def rotate(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: void Do not return anything, modify nums in-place instead.
        """
        for i in range(k):
            previous = nums[-1]
            for j in range(len(nums)):
                nums[j], previous = previous, nums[j]

s = Solution1()
nums = [1, 2, 3, 4, 5, 6, 7]
k = 3
s.rotate(nums, k)
assert nums == [5, 6, 7, 1, 2, 3, 4]

nums = [-1, -100, 3, 99]
k = 2
s.rotate(nums, k)
assert nums == [3,99,-1,-100]

2. Using Extra Array

Algorithm We use an extra array in which we place every element of the array at its correct position i.e. the number at index ii in the original array is placed at the index (i + k) % length of array. Then, we copy the new array to the original one.

class Solution2(object):
    """
    Time: O(n). One pass is used to put the numbers in the new array.
                And another pass to copy the new array to the original one.
    Space: O(n). Another array of the same size is used.
    """
    def rotate(self, nums, k) -> None:
        """
        :type nums: List[int]
        :type k: int
        :rtype: void Do not return anything, modify nums in-place instead.
        """
        n = len(nums)
        a = [0] * n
        for i in range(n):
            a[(i + k) % n] = nums[i]

        nums[:] = a

s = Solution2()
nums = [1, 2, 3, 4, 5, 6, 7]
k = 3
s.rotate(nums, k)
assert nums == [5, 6, 7, 1, 2, 3, 4]

nums = [-1, -100, 3, 99]
k = 2
s.rotate(nums, k)
assert nums == [3,99,-1,-100]

3. Using Cyclic Replacements

Algorithm We can directly place every number of the array at its required correct position. But if we do that, we will destroy the original element. Thus, we need to store the number being replaced in a temptemp variable. Then, we can place the replaced number (temp) at its correct position and so on, N times, where N is the length of array. We have chosen nn to be the number of replacements since we have to shift all the elements of the array(which is N). But, there could be a problem with this method, if n % k = 0 where k = k % n (since a value of k larger than N eventually leads to a kk equivalent to k % n). In this case, while picking up numbers to be placed at the correct position, we will eventually reach the number from which we originally started. Thus, in such a case, when we hit the original number’s index again, we start the same process with the number following it.

Now let’s look at the proof of how the above method works. Suppose, we have nn as the number of elements in the array and k is the number of shifts required. Further, assume n % k = 0. Now, when we start placing the elements at their correct position, in the first cycle all the numbers with their index i satisfying i % k = 0 get placed at their required position. This happens because when we jump k steps every time, we will only hit the numbers k steps apart. We start with index i = 0, having i % k = 0. Thus, we hit all the numbers satisfying the above condition in the first cycle. When we reach back the original index, we have placed n / k elements at their correct position, since we hit only that many elements in the first cycle. Now, we increment the index for replacing the numbers. This time, we place other n / k elements at their correct position, different from the ones placed correctly in the first cycle, because this time we hit all the numbers satisfy the condition i % k = 1. When we hit the starting number again, we increment the index and repeat the same process from i = 1 for all the indices satisfying i % k == 1. This happens till we reach the number with the index i % k = 0 again, which occurs for i = k. We will reach such a number after a total of k cycles. Now, the total count of numbers exclusive numbers placed at their correct position will be k × N/k = N. Thus, all the numbers will be placed at their correct position.

Look at the following example to clarify the process:

nums: [1, 2, 3, 4, 5, 6] k: 2

class Solution3(object):
    def rotate(self, nums, k) -> None:
        """
        :type nums: List[int]
        :type k: int
        :rtype: void Do not return anything, modify nums in-place instead.
        """
        n = len(nums)
        k %= n

        start = count = 0
        while count < n:
            current, prev = start, nums[start]
            while True:
                next_idx = (current + k) % n
                nums[next_idx], prev = prev, nums[next_idx]
                current = next_idx
                count += 1

                if start == current:
                    break
            start += 1

s = Solution3()
nums = [1, 2, 3, 4, 5, 6, 7]
k = 3
s.rotate(nums, k)
assert nums == [5, 6, 7, 1, 2, 3, 4]

nums = [-1, -100, 3, 99]
k = 2
s.rotate(nums, k)
assert nums == [3,99,-1,-100]

4. Using Reverse

Algorithm This approach is based on the fact that when we rotate the array k times, k % n elements from the back end of the array come to the front and the rest of the elements from the front shift backwards.

In this approach, we firstly reverse all the elements of the array. Then, reversing the first k elements followed by reversing the rest n-k elements gives us the required result.

Let n = 7 and k = 3.

Original List                   : 1 2 3 4 5 6 7
After reversing all numbers     : 7 6 5 4 3 2 1
After reversing first k numbers : 5 6 7 4 3 2 1
After revering last n-k numbers : 5 6 7 1 2 3 4 --> Result

class Solution4(object):
    """
    Reverse
    Time: O(N). N elements are reversed a total of three times.
    Space: O(1). No extra space is used.
    """
    def reverse(self, nums, start, end):
        while start < end:
            nums[start], nums[end - 1] = nums[end - 1], nums[start]
            start += 1
            end -= 1

    def rotate(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: void Do not return anything, modify nums in-place instead.
        """
        n = len(nums)
        k %= n

        self.reverse(nums, 0, n)
        self.reverse(nums, 0, k)
        self.reverse(nums, k, n)

    def rotate2(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: void Do not return anything, modify nums in-place instead.
        """
        nums[:] = nums[len(nums) - k:] + nums[:len(nums) - k]

s = Solution4()
nums = [1, 2, 3, 4, 5, 6, 7]
k = 3
s.rotate(nums, k)
assert nums == [5, 6, 7, 1, 2, 3, 4]

nums = [-1, -100, 3, 99]
k = 2
s.rotate(nums, k)
assert nums == [3,99,-1,-100]

5. Using GCD

from math import gcd

class Solution5(object):
    def rotate(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: void Do not return anything, modify nums in-place instead.
        """
        k %= len(nums)
        num_cycles = gcd(len(nums), k)
        cycle_len = len(nums) // num_cycles
        for i in range(num_cycles):
            self.apply_cycle_permutation(k, i, cycle_len, nums)

    def apply_cycle_permutation(self, k, offset, cycle_len, nums):
        tmp = nums[offset]
        for i in range(1, cycle_len):
            nums[(offset + i * k) % len(nums)], tmp = tmp, nums[(offset + i * k) % len(nums)]
        nums[offset] = tmp

s = Solution5()
nums = [1, 2, 3, 4, 5, 6, 7]
k = 3
s.rotate(nums, k)
assert nums == [5, 6, 7, 1, 2, 3, 4]

nums = [-1, -100, 3, 99]
k = 2
s.rotate(nums, k)
assert nums == [3,99,-1,-100]

class Solution6(object):
    def rotate(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: void Do not return anything, modify nums in-place instead.
        """
        count = 0
        start = 0
        while count < len(nums):
            curr = start
            prev = nums[curr]
            while True:
                idx = (curr + k) % len(nums)
                nums[idx], prev = prev, nums[idx]
                curr = idx
                count += 1
                if start == curr:
                    break
            start += 1

s = Solution6()
nums = [1, 2, 3, 4, 5, 6, 7]
k = 3
s.rotate(nums, k)
assert nums == [5, 6, 7, 1, 2, 3, 4]

nums = [-1, -100, 3, 99]
k = 2
s.rotate(nums, k)
assert nums == [3,99,-1,-100]

See also:

https://leetcode.com/problems/rotate-array